package com.careercup.question.id57945;

import java.util.Stack;

public class Solution {
	private static class Node {
		private Node left, right;
		private char ch;
		public Node(char ch) {
			this.ch = ch;
		}
		public void printZigZag() {
			Stack<Node> s1 = new Stack<Node>(), s2 = new Stack<Node>();
			s1.add(this);
			while(!s1.isEmpty()) {
				while(!s1.isEmpty()) {
					Node n = s1.pop();
					System.out.println(n.ch);
					if(n.left != null)
						s2.push(n.left);
					if(n.right != null)
						s2.push(n.right);
				}
				while(!s2.isEmpty()) {
					Node n = s2.pop();
					System.out.println(n.ch);
					if(n.right != null)
						s1.push(n.right);
					if(n.left != null)
						s1.push(n.left);
				}
			}
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		 Node a = new Node('a'), b = new Node('b');
		 Node c = new Node('c'), d = new Node('d');
		 Node e = new Node('e'), f = new Node('f');
		 Node g = new Node('g'), h = new Node('h');
		 Node i = new Node('i'), j = new Node('j');
		 Node k = new Node('k'), l = new Node('l');
		 Node m = new Node('m'), n = new Node('n');
		 Node o = new Node('o');
		 a.left = b;
		 a.right = c;
		 b.left = d;
		 b.right = e;
		 c.left = f;
		 c.right = g;
		 d.left = h;
		 d.right = i;
		 e.left = j;
		 e.right = k;
		 f.left = l;
		 f.right = m;
		 g.left = n;
		 g.right = o;
		 a.printZigZag();
	}
}
